#include<map> #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; void Rd(int&res){ res=0;char c; while(c=getchar(),c<48); do res=res*10+(c&15); while(c=getchar(),c>47); } const int N=1001,P=233; int stk[N],top,ans[N]; struct Treap{ struct node{ int ch[2],key,val,sz,flag; }tree[N]; void pushup(int&p){ tree[p].sz=tree[tree[p].ch[0]].sz+tree[tree[p].ch[1]].sz+1; } void maintain(int&p,int flag){ int val=tree[p].val; ans[val]=max(ans[val],flag); tree[p].flag=max(tree[p].flag,flag); } void pushdown(int&p){ if(!tree[p].flag)return; int ls=tree[p].ch[0],rs=tree[p].ch[1]; if(ls)maintain(ls,tree[p].flag); if(rs)maintain(rs,tree[p].flag); tree[p].flag=0; } void rotate(int&p,int d){ int k=tree[p].ch[d^1]; pushdown(p),pushdown(k); tree[p].ch[d^1]=tree[k].ch[d]; tree[k].ch[d]=p; pushup(p),pushup(k);p=k; } void insert(int&p,int x){ if(!p){ p=stk[top--]; tree[p].key=rand(),tree[p].val=x,tree[p].sz=1; tree[p].ch[0]=tree[p].ch[1]=tree[p].flag=0; }else{ pushdown(p); tree[p].sz++; bool d=x>tree[p].val; insert(tree[p].ch[d],x); if(tree[p].key<tree[tree[p].ch[d]].key)rotate(p,d^1); } pushup(p); } void erase(int&p,int x){ pushdown(p); tree[p].sz--; if(tree[p].val==x){ if(!tree[p].ch[0])stk[++top]=p,p=tree[p].ch[1]; else if(!tree[p].ch[1])stk[++top]=p,p=tree[p].ch[0]; else{ bool d=tree[tree[p].ch[0]].key>tree[tree[p].ch[1]].key; rotate(p,d);erase(tree[p].ch[d],x); } }else{ bool d=x>tree[p].val; erase(tree[p].ch[d],x); } if(p)pushup(p); } int size(int p){ return tree[p].sz; } }T; typedef unsigned long long ull; map<ull,int>rt; ull hash_val[N],p[101]; char str[N][101]; int n,l,m; void INSERT(int x){ T.insert(rt[hash_val[x]],x); int t=rt[hash_val[x]]; T.maintain(t,T.size(t)); } void DELETE(int x){ T.erase(rt[hash_val[x]],x); } int main(){ Rd(n),Rd(l),Rd(m); for(int i=n;i>=1;i--)stk[++top]=i; p[0]=1; for(int i=1;i<=l;i++)p[i]=p[i-1]*P; for(int i=1;i<=n;i++){ scanf("%s",str[i]); for(int j=0;j<l;j++) hash_val[i]=hash_val[i]*P+str[i][j]; INSERT(i); } for(int i=1;i<=m;i++){ int a,b,c,d; Rd(a),Rd(b),Rd(c),Rd(d); DELETE(a); if(a!=c)DELETE(c); hash_val[a]=hash_val[a]-p[l-b]*str[a][b-1]+p[l-b]*str[c][d-1]; hash_val[c]=hash_val[c]-p[l-d]*str[c][d-1]+p[l-d]*str[a][b-1]; swap(str[a][b-1],str[c][d-1]); INSERT(a); if(a!=c)INSERT(c); } for(int i=1;i<=n;i++)DELETE(i); for(int i=1;i<=n;i++){ printf("%d\n",ans[i]); } return 0; }
|